DROPS

Document

DOI: 10.4230/LIPIcs.CPM.2021.23

Efficient Algorithms for Counting Gapped Palindromes

Authors: Andrei Popa and Alexandru Popa

Published in: LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)

Abstract

A gapped palindrome is a string uvu^{R}, where u^{R} represents the reverse of string u. In this paper we show three efficient algorithms for counting the occurrences of gapped palindromes in a given string S of length N. First, we present a solution in O(N) time for counting all gapped palindromes without additional constraints. Then, in the case where the length of v is constrained to be in an interval [g, G], we show an algorithm with running time O(N log N). Finally, we show an algorithm in O(N log² N) time for a more general case where we count gapped palindromes uvu^{R}, where u^{R} starts at position i with g(i) ≤ v ≤ G(i), for all positions i.

Cite as

Andrei Popa and Alexandru Popa. Efficient Algorithms for Counting Gapped Palindromes. In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, pp. 23:1-23:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{popa_et_al:LIPIcs.CPM.2021.23,
  author =	{Popa, Andrei and Popa, Alexandru},
  title =	{{Efficient Algorithms for Counting Gapped Palindromes}},
  booktitle =	{32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)},
  pages =	{23:1--23:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-186-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{191},
  editor =	{Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.23},
  URN =		{urn:nbn:de:0030-drops-139746},
  doi =		{10.4230/LIPIcs.CPM.2021.23},
  annote =	{Keywords: pattern matching, gapped palindromes, suffix tree}
}

Search Results

Documents authored by Popa, Andrei

Efficient Algorithms for Counting Gapped Palindromes

Abstract

Cite as

Thanks for your feedback!

Could not send message